class LstNode():
    def __init__(self,val):
        self.key=val
        self.represent=self
        self.next=None
    def __str__(self):
        return str(self.key)
    def __repr__(self):
        return str(self)
class Lst():
    def __init__(self,val):
        self.head=LstNode(val)
        self.tail=self.head
        self.length=1
    def extend(self,other):
        self.tail.next=other.head
        curr=other.head
        while curr is not None:
            curr.represent=self.head
            curr=curr.next
        self.tail=other.tail
        self.length+=other.length
    def __iter__(self):
        curr=self.head
        while curr is not None:
            yield curr.key
            curr=curr.next
    def __str__(self):
        return str([node for node in self])
    def __repr__(self):
        return str(self)
    def __len__(self):
        return self.length

class Disjoint_sets():
    def __init__(self):
        self.represent={}
        self.unions={}
    def makeset(self, val):
        self.represent[val]=len(self.represent)
        self.unions[val]=(Lst(val))
    def find(self, val):
        return self.represent[val]
    def union(self,val1,val2):
        repr1=self.represent[val1]
        len1=len(self.unions[repr1])
        repr2=self.represent[val2]
        len2=len(self.unions[repr2])
        if len1>=len2:
            for val in self.unions[repr2]:
                self.represent[val]=repr1
            self.unions[repr1].extend(self.unions[repr2])
            del self.unions[repr2]
        else:
            for val in self.unions[repr1]:
                self.represent[val]=repr2
            self.unions[repr2].extend(self.unions[repr1])
            del self.unions[repr1]
        
if __name__=='__main__':
    a=Disjoint_sets()
    a.makeset(0)
    a.makeset(1)
    a.makeset(2)
    a.makeset(3)
    a.makeset(4)
    print 'node:represent ', a.represent
    a.union(0,2)
    a.union(3,4)
    a.union(0,3)
    a.union(1,2)
    print 'node:represent ', a.represent
    print 'represent:sets ', a.unions
